#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#include "fnct.h"
#include "time.h"

#define MAX 12

static int len;
void quick_sort(int A[], int l, int r){
	int index;
	if(r > (len - 1) || l < 0) return;
	if(l < r){
		index = randomized_partition(A, l, r);
		quick_sort(A, l, index - 1);
		quick_sort(A, index + 1, r);
	}
}

int partition(int A[], int l, int r){
	int i = l-1, j = l;
	int x = A[r];
	for(;j < r; j++){
		if(A[j] < x){
			i++;
			swap(&A[i],&A[j]);
		}
	}
	swap(&A[i+1], &A[r]);
	return i+1;
}

int randomized_partition(int A[], int l, int r){
	int i;
	srand(time(NULL));
	i = rand()%(r-l)+l;
	swap(&A[i], &A[r]);
	return partition(A, l, r);
}

int main(void){
	int A[MAX] = {10, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11};
	len = sizeof(A)/sizeof(int);
	print_array(A, len);
	quick_sort(A, 0, len - 1);
	print_array(A, len);
	exit(0);
}
